﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace Utility.DataStructure
{
	/// <summary>
	/// A multilayer linked list
	/// Ordered Insert: O(lnN)
	/// Remove Head: O(1)
	/// Space: O(N)
	/// </summary>
	/// <typeparam name="TK">sorting key</typeparam>
	/// <typeparam name="TV">data</typeparam>
	public class SortedLinkedList<TK, TV> : IEnumerable<KeyValuePair<TK, TV>>
		where TK : IComparable<TK>
	{
		Node origin;

		public int Count { get; private set; } = 0;

		//constructor
		public SortedLinkedList ()
		{
			Init ();
		}

		void Init ()
		{
			origin = Node.Spawn ();
			var pivot = Node.Spawn ();
			origin.up = pivot;
			origin.pivot = pivot;
			pivot.down = origin;
			pivot.size = 1;
		}

		public void Clear ()
		{
			var curr = origin;
			while (curr != null)
			{
				var next = curr.next;
				RemoveColumn (curr);
				curr = next;
			}
			Init ();
			Count = 0;

			void RemoveColumn (Node bottom)
			{
				DataNode.Despawn (bottom.data);
				var _curr = bottom;
				while (_curr != null)
				{
					var _up = _curr.up;
					Node.Despawn (_curr);
					_curr = _up;
				}
			}
		}

		public bool ContainsKey (TK key)
		{
			return origin.FindBottomNodePrevTo (key).data.key.CompareTo (key) == 0;
		}

		/// <summary>
		/// find the last value with given key
		/// </summary>
		/// <param name="key"></param>
		/// <param name="value"></param>
		/// <returns></returns>
		public bool TryGetValue (TK key, out TV value)
		{
			var node = origin.FindBottomNodePrevTo (key);
			if (node.data.key.CompareTo (key) == 0)
			{
				value = node.data.value;
				return true;
			}
			else
			{
				value = default;
				return false;
			}
		}

		/// <summary>
		/// Auto sorted insertion
		/// Time Complexity: O(lnN)
		/// </summary>
		/// <param name="key"></param>
		/// <param name="value"></param>
		public void Add (TK key, TV value)
		{
			origin.AddDataNode (DataNode.Spawn (key, value));
			Count++;
		}

		public KeyValuePair<TK, TV> Peak ()
		{
			if (Count == 0)
			{
				throw new InvalidOperationException ();
			}
			return origin.next.data.KVPair;
		}

		public TK PeakKey ()
		{
			if (Count == 0)
			{
				throw new InvalidOperationException ();
			}
			return origin.next.data.KVPair.Key;
		}

		public TV PeakValue ()
		{
			if (Count == 0)
			{
				throw new InvalidOperationException ();
			}
			return origin.next.data.KVPair.Value;
		}


		public KeyValuePair<TK, TV> Pop ()
		{
			if (Count == 0)
			{
				throw new InvalidOperationException ();
			}

			var pair = origin.next.data.KVPair;
			origin.next.RemoveColumn ();
			Count--;
			return pair;
		}

		public bool TryFindNextTo (TK key, out TK dataKey, out TV dataValue)
		{
			var node = origin.FindBottomNodePrevTo (key).next;
			if (node == null)
			{
				dataKey = default;
				dataValue = default;
				return false;
			}
			var data = node.data;
			dataKey = data.key;
			dataValue = data.value;
			return true;
		}

		public bool TryFindNextTo (TK key, out KeyValuePair<TK, TV> pair)
		{
			var result = TryFindNextTo (key, out var k, out var v);
			pair = new KeyValuePair<TK, TV> (k, v);
			return result;
		}

		public bool TryFindPrevTo (TK key, out TK dataKey, out TV dataValue)
		{
			var node = origin.FindBottomNodePrevTo (key);
			if (node == origin)
			{
				dataKey = default;
				dataValue = default;
				return false;
			}
			var data = node.data;
			dataKey = data.key;
			dataValue = data.value;
			return true;
		}

		public bool TryFindPrevTo (TK key, out KeyValuePair<TK, TV> pair)
		{
			var result = TryFindPrevTo (key, out var k, out var v);
			pair = new KeyValuePair<TK, TV> (k, v);
			return result;
		}

		#region IEnumerator
		IEnumerator<KeyValuePair<TK, TV>> IEnumerable<KeyValuePair<TK, TV>>.GetEnumerator ()
		{
			var curr = origin;
			while (curr.next != null)
			{
				curr = curr.next;
				yield return curr.data.KVPair;
			}
		}

		public IEnumerable<TK> Keys
		{
			get
			{
				var curr = origin;
				while (curr.next != null)
				{
					curr = curr.next;
					yield return curr.data.key;
				}
			}
		}

		public IEnumerable<TV> Values
		{
			get
			{
				var curr = origin;
				while (curr.next != null)
				{
					curr = curr.next;
					yield return curr.data.value;
				}
			}
		}

		IEnumerator IEnumerable.GetEnumerator ()
		{
			var curr = origin;
			while (curr.next != null)
			{
				curr = curr.next;
				yield return curr.data.KVPair;
			}
		}
		#endregion
		#region node class
		class Node
		{
			const byte MaxSize = 5;

			#region pooling
			static Stack<Node> objPool = new Stack<Node> ();

			public static Node Spawn ()
			{
				return objPool.Count > 0 ? objPool.Pop () : new Node ();
			}

			public static void Despawn (Node node)
			{
				node.Reset ();
				objPool.Push (node);
			}
			#endregion

			public Node prev, next, up, down;
			public Node pivot;//the up node of cell head
			public byte size;
			public DataNode data;

			Node () { }

			void Reset ()
			{
				prev = null;
				next = null;
				pivot = null;
				up = null;
				down = null;
				size = 0;
				data = null;
			}

			//find base node with biggest key that smaller then input key
			public Node FindBottomNodePrevTo (TK key)
			{
				if (next == null || key.CompareTo (next.data.key) < 0)
				{
					return down == null ? this : down.FindBottomNodePrevTo (key);
				}
				else
				{
					return next.FindBottomNodePrevTo (key);
				}
			}

			//split to two cell if the current size is too big
			void TrySplit ()
			{
				if (size > MaxSize)
				{
					byte size_0 = (byte)(size / 2);
					byte size_1 = (byte)(size - size_0);

					//find new pivot base
					Node newPivotBase = down;
					for (int i = 0; i < size_0; i++)
					{
						newPivotBase = newPivotBase.next;
					}
					//new pivot
					Node newPivot = Spawn ();
					newPivot.down = newPivotBase;
					newPivotBase.up = newPivot;
					newPivot.data = newPivotBase.data;
					if (next != null)
					{
						next.prev = newPivot;
						newPivot.next = next;
					}
					newPivot.prev = this;
					next = newPivot;
					Node curr = newPivotBase;
					for (int i = 0; i < size_1; i++)
					{
						curr.pivot = newPivot;
						curr = curr.next;
					}

					size = size_0;
					newPivot.size = size_1;

					//pivot
					if (pivot == null)
					{
						pivot = Spawn ();
						pivot.down = this;
						up = pivot;
						pivot.size = 1;
					}
					newPivot.pivot = pivot;
					pivot.size++;

					//try split
					TrySplit ();
					newPivot.TrySplit ();
					pivot.TrySplit ();

				}
			}

			public void InsertNext (Node node)
			{
				if (down == null)
				{
					if (next != null)
					{
						next.prev = node;
						node.next = next;
					}
					next = node;
					node.prev = this;
					node.pivot = pivot;
					pivot.size++;
					pivot.TrySplit ();
				}
				else
				{
					down.InsertNext (node);
				}
			}

			//call on pivot
			public void AddDataNode (DataNode dataNode)
			{
				if (pivot == null)
				{
					var node = Spawn ();
					node.data = dataNode;

					FindBottomNodePrevTo (dataNode.key).InsertNext (node);
				}
				else
				{
					pivot.AddDataNode (dataNode);
				}
			}

			//call on top
			public void RemoveColumn ()
			{
				if (up == null)
				{
					DataNode.Despawn (data);
					var curr = this;
					while (curr != null)
					{
						var down = curr.down;
						Remove (curr);
						curr = down;
					}
				}
				else
				{
					up.RemoveColumn ();
				}

				void Remove (Node n)
				{
					if (n == null)
					{
						return;
					}

					var curr = n.down;
					var newPivot = n.prev;
					for (int i = 0; i < n.size; i++)
					{
						curr.pivot = newPivot;
						newPivot.size++;
						curr = curr.next;
					}
					n.pivot.size--;

					if (n.next != null)
					{
						n.next.prev = n.prev;
					}
					n.prev.next = n.next;

					Despawn (n);
				}
			}

			public override string ToString ()
			{
				return data?.ToString () ?? "empty";
			}
		}

		class DataNode
		{
			static Stack<DataNode> objPool = new Stack<DataNode> ();
			public static DataNode Spawn (TK key, TV value)
			{
				var item = objPool.Count > 0 ? objPool.Pop () : new DataNode ();
				item.Init (key, value);
				return item;
			}

			public static void Despawn (DataNode obj)
			{
				if (obj != null)
				{
					obj.Clear ();
					objPool.Push (obj);
				}
			}

			public TK key;
			public TV value;

			public KeyValuePair<TK, TV> KVPair => new KeyValuePair<TK, TV> (key, value);

			void Init (TK key, TV value)
			{
				this.key = key;
				this.value = value;
			}

			void Clear ()
			{
				key = default;
				value = default;
			}

			public override string ToString ()
			{
				return KVPair.ToString ();
			}
		}

		#endregion
	}
}